/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
//class Solution {
//public:
//    TreeNode* pcur;
//
//    void _flatten(TreeNode* root)
//    {
//        if (root == nullptr) return;
//        pcur->right = new TreeNode(root->val);
//        pcur = pcur->right;
//        _flatten(root->left);
//        _flatten(root->right);
//        // delete root;
//    }
//
//    void flatten(TreeNode*& root) {
//        if (root == nullptr) return;
//        TreeNode* ansR = new TreeNode();
//        pcur = ansR;
//        _flatten(root);
//        root = ansR->right;
//    }
//};

#include<iostream>
#include<queue>
using namespace std;

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    queue<TreeNode*> qu;

    void _flatten(TreeNode* root)
    {
        if (root == nullptr) return;
        qu.push(root);
        _flatten(root->left);
        _flatten(root->right);
    }

    void flatten(TreeNode*& root) {
        if (root == nullptr) return;
        _flatten(root);
        qu.push(nullptr);
        TreeNode* pcur = nullptr;
        while (qu.front()) {
            pcur = qu.front();
            qu.pop();
            pcur->left = nullptr;
            pcur->right = qu.front();
        }
    }
};



